package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/12 9:01
 * @description :4道
 * 城墙
 * persevere to last
 * 2021.11.12
 * 李红磊
 * 2021年11月12日18:07:25
 */
public class t20211112 {

    //375.猜数字大小
    public int getMoneyAmount(int n) {
        if (n == 1) return 0;

        int[][] dp = new int[n + 1][n + 1];
    /*
        do[i][j]:表示从i-j范围内猜数用到的最少金钱数
     */
        //按列来，从第2列开始
        for (int j = 2; j <= n; j++) {
            //按行来，从下往上
            for (int i = j - 1; i >= 0; i--) {
                //计算两端
                int a = Math.min(i + dp[i + 1][j], j + dp[i][j - 1]);//取出两端中最小使用最小花费可以猜出数的那一个端点
                //如 1 2 3，目标数为2。我们先从左端点开始，最多需花费1元即可猜出结果。 从右端点开始，最多需花费3元
                //则我们得出1元
                int b = Integer.MAX_VALUE;

                //算除了两端的每一个分割点（中间的点
                for (int k = i + 1; k <= j - 1; k++) {
                    int temp = k + Math.max(dp[i][k - 1], dp[k + 1][j]);//如选择k为猜数起点，最多花费的钱
                    b = Math.min(b, temp);//不断刷新中间节点的值，
                }

                dp[i][j] = Math.min(b, a);//将中间节点需要的钱和两端需要的钱进行比较，得出需要钱最少的
                //dp[i][j] = Math.min(dp[i][j], i + dp[i + 1][j]);//左端
                //dp[i][j] = Math.min(dp[i][j], j + dp[i][j - 1]);//右端

            }

        }

        return dp[1][n];
    }

    private int is(int x) {
        int sum = 0;
        while (x > 0) {
            int tem = x % 10;
            sum += tem * tem;
            x /= 10;
        }
        return sum;
    }

    //202.快乐数
    public boolean isHappy(int n) {
        HashSet<Integer> hashSet = new HashSet<>();

        while (n != 1 && !hashSet.contains(n)) {
            hashSet.add(n);
            n = is(n);
        }

        return n == 1;
    }

    private int squareNum(int x) {
        int sum = 0;
        while (x > 0) {
            int t = x % 10;
            sum += t * t;
            x /= 10;
        }
        return sum;
    }

    public boolean isHappy2(int n) {
        if (n == 1) return true;
        int slow = n, fast = n;

        do {
            slow = squareNum(slow);
            fast = squareNum(fast);
            fast = squareNum(fast);
        } while (fast != slow);

        return slow == 1;

    }

    //149.直线上最多的点
    public int maxPoints(int[][] points) {
        if (points == null || points.length == 0) return 0;

        int len = points.length;//所有点的数量
        int res = 1;

        for (int i = 0; i < len; i++) {
            //第一个点
            int[] m1 = points[i];
            for (int j = i + 1; j < len; j++) {
                //第二个点
                int[] m2 = points[j];
                // 由2个点确定下来的斜率 得出在该斜率上的所有点
                // 这里为0是因为下面会遍历所有的点所以不需要设置起始值
                int count = 0;
                for (int k = 0; k < len; k++) {
                    //第三个点
                    int[] m3 = points[k];

                    // 2个斜率相同时代表这2个点处在同一个线上
                    if (m1 == m3 || m2 == m3) {
                        count += 1;
                    } else if ((m1[1] - m2[1]) * (m1[0] - m3[0]) == (m1[0] - m2[0]) * (m1[1] - m3[1])) {
                        count += 1;
                    }

                    //比较值
                    res = Math.max(res, count);

                }
            }

        }

        return res;
    }


    public static void main(String[] args) {
        t20211112 t20211112 = new t20211112();
        Random random = new Random();
        System.out.println(t20211112.maxPoints(new int[][]{
                {1, 1},
                {1, 1}
        }));


    }


}

//384.打乱数组
class Solution {

    private int[] array;
    private int[] original;
    private Random random = new Random();

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }

    private List getCopyArr(int[] arr) {
        ArrayList<Integer> aux = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            aux.add(arr[i]);
        }
        return aux;
    }


    public int[] reset() {
        array = original;
        original = original.clone();
        return array;
    }

    public int[] shuffle() {
        List aux = getCopyArr(array);

        for (int i = 0; i < array.length; i++) {
            int index = random.nextInt(aux.size());
            array[i] = (int) aux.get(index);
            aux.remove(index);
        }
        return array;
    }

    public static void main(String[] args) {


    }
}

class Solution2 {

    private int[] array;
    private int[] original;
    private Random random = new Random();

    public Solution2(int[] nums) {
        array = nums;
        original = nums.clone();
    }

    private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private int randRange(int min, int max) {
        return random.nextInt(max - min) + min;
    }

    public int[] reset() {
        array = original;
        original = original.clone();
        return array;
    }

    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) {
            swap(i, randRange(i, array.length));
        }

        return array;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2(new int[]{1, 2, 3});


    }
}